Voxel Model Generation using Wave Function Collapse



The “wave function collapse”(WFC) algorithm builds a grid of pre-defined tiles ensuring that the tiles properly connect to their neighbours, for example a road tile must neighbour another road tile following the same direction or an intersection tile. In this project we will use the WFC algorithm to produce random 3D voxel maps, like the one below. alt text

The WFC algorithm takes in an archetypical input, and produces procedurally-generated outputs that look like it (overlapping generation). It can also take a set of tiles and constraints, and generate an image using these tiles that match these contraints (tiled generation). It is most commonly used to create images, but is also capable of building towns in higher dimensions.

Goals and Deliverables


WFC algorithm is used in multiples implementations, the main concept of the algorithm is quite straightforward but a lot of optimization and variations can be done. During this project, we will focus on three things:

  • Build a 3D simple tiled engine: Take a set of voxels (File format to process voxels, cf MagicaVoxel) and a set of neighbourhood rules to produce a 3D scene that match the constraints rules. We will first produce .vox files to check that our implementation is correct and then render the model using openGL.
  • Design voxels : Build a set of voxels (.vox file) that can be use to design a meaningful world.
  • Design meaningful rules : Write rules for the set of voxel created that can lead to a relevant scene generation with the WFC algorithm.

Optionnal Extensions

In order to improve our resulting scenes we will add some extensions to the project, depending on how much time we have. The potential extensions are describe below:

  • Animate the parts entering the scene : The algorithm as described before only render the final result of the WFC algorithm. We could display instead, each Voxel choose by the algorithm one by one with a nice animation to produce a step by step video of the generation.

  • Bézier curves for camera trajectory : It could be nice to allow the user to move the camera nicely in the produced scene using Bezier curve

  • Bloom + emissive lights in the scene : To produce a more realistic scene, we could add Bloom and emissive light to the rendering pipeline.

  • Screen space reflections : Another extension to make the scene more realistic, add reflection on objects.

  • Ambient occlusion : Ambient occlusion is a shading and rendering technique used to calculate how exposed each point in a scene is to ambient lighting. For example, the interior of a tube is typically more occluded (and hence darker) than the exposed outer surfaces, and the deeper you go inside the tube, the more occluded (and darker) the lighting become.

  • Infinite world generation : Once the user can move the camera in the scene, it could be interesting to infinitely generate scene when the user move further away.

Schedule


You can find in the array below some important dates during the project development:

Event Due Date
Proposal due Thursday April 11, 1pm
Proposal feedback by Thursday April 18
Project work begins Friday April 19
Learn about WFC and report Thursday April 25th
Design voxels model to feed WFC Thursday May 2nd
Working 3D tiled model Thursday May 16
Milestone report due Thursday May 16, 1pm
Working rules for the model Thursday May 23
Animate parts entering the scene Thursday May 23
Bezier for camera trajectory Tuesday May 28
Final presentation video due Tuesday May 28, 1pm
Final report webpage due Friday May 31, 1pm

Technical Approach


WFC algorithm implementation

BLABLABLA

Voxels design and Rules implementation

We first begin to build a set of voxels block to feed our algorithm. This step was quite time consuming since we needed to think about how each block will interact with each over. We builded a set of 16 different blocks to define the world, some of them are shown below:

Once we had our differents pieces of the puzzle, we needed to write down rules to define which block can be placed next to each other taking in account the rotation and the symmetry of each piece. One of the main problems that occured during the development was the low percentage of success rate. Indeed the more complex the rules/constraints are, the less likely is for the algorithm to find a stable configuration. Currently, there is about 200 rules with a success rate of about 4% to obtain the models shown in the results part. However, the current rules enables for complex structure generation (Bridge-connected high buildings, doors, balconies, roads, stairs…). The rules are located in the same folder as blocks : World/data.xml.

Rendering the scene

We started with the SolarSystemViewer source code as a foundation for our rendering engine. The entine scene is rendered as a single mesh in order to improve performances. Phong lighting and shadows (with a shadow map) were implemented with shaders. Files related to rendering are located under /src/rendering/.

Bezier Curve and camera trajectory

BLABLABLA

Animate the parts entering the scene

BLABLABLA

Results


Resources and technologies used


Technologies

  • C++
  • A 3D rendering engine (OpenGL via LWJGL)
  • MagicaVoxel

Resources :

We will use the homework SolarSystem base project in C++ to help us integrate OpenGl.

 




A work by Antoine Crettenand, Louis Vialar, François Quellec

https://github.com/Fanfou02/RandomTilemapGeneration